package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/4 15:02
 * @DESCRIPTION
 */

// 给你一个 无重复元素 的（正数）整数数组 candidates 和一个目标整数 target ，
// 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，
// 并以列表形式返回。你可以按 任意顺序 返回这些组合。
// candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
// 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
public class 组合总数 {
    //自己写出
    LinkedList<Integer> path=new LinkedList<>();//路径
    List<List<Integer>> res=new ArrayList<>();//最终结果
    //和组合最大的不同就是，他可以重复利用自己，在循环的时候注意一下就行
    public List<List<Integer>> method1(int[] candidates, int target) {
        recursion(0,candidates,target);
        return res;
    }
    public void recursion(int head,int[] candidates, int differ){
        //在递归头来判断differ，不要在循环体中去判断，否则会容易出错
        if(differ<=0){
            if(differ==0){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = head; i <candidates.length; i++) {
            path.add(candidates[i]);
            recursion(i,candidates,differ-candidates[i]);
            path.removeLast();
        }
    }
    //第二遍写的时候很不顺畅
    //他有两个特点
    //一个是元素可重复使用
    //另外一个是利用元素和来判断结束，而不是元素的数量，也不同于子集
    public List<List<Integer>> practice(int[] candidates, int target) {
        recursionPractice(candidates,target,0);
        return res;
    }

    private void recursionPractice(int[] candidates, int target,int index) {
        if(target<=0){
            if(target==0){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            path.add(candidates[i]);
            recursionPractice(candidates,target-candidates[i],i);
            path.removeLast();
        }
    }

    //类似于组合 但不同于组合
    //不同的点在于在往深度时，可以重复利用自己
    //而在广度上，和组合是一样的，当遍历到i为止时，不能再使用i前面的元素，避免重复
    //此题目是可以剪枝来提高速度的
    public List<List<Integer>> practice2(int[] candidates, int target) {
        recursionPractice2(candidates,target,0,0);
        return res;
    }
    public void recursionPractice2(int[]candidates,int target,int sum,int startIndex){
        if(sum>=target){
            if(sum==target){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            path.add(candidates[i]);
            recursionPractice2(candidates,target,sum+candidates[i],i);
            path.removeLast();
        }
    }
}
